#include "Format.h"

class ShellSort {
public:
    ShellSort();

    ShellSort(int *arr, int num) {
        ShellSort();
        this->sort(arr, num);
        Format::format(arr, num);
    }
    ~ShellSort();

private:
    int sort(int arr[], int num);
};

ShellSort::ShellSort() {
}

ShellSort::~ShellSort() {
}

int ShellSort::sort(int *arr, int n) {

    /*�����Ϊinc��Ԫ�ط�Ϊһ�飬
    ��inc=2������Ϊ1��2��3��4��5��6��
    ��һ��Ϊ1��3��5��Ȼ��ÿ�����������Сinc���ϴν���ٴ�����
     */
    int inc, moveCount = 0, compareCount = 0, j;
    for (inc = n / 2; inc > 0; inc /= 2) {
        //�涨ÿ��inc��СΪԭ��һ��
        for (int i = inc; i < n; i++) {
            //���ò���������Ϊÿ�������ʽ
            int temp = arr[i];
            for (j = i - inc; j >= 0 && temp < arr[j]; j -= inc) {
                arr[j + inc] = arr[j];
                compareCount += 2;
                moveCount;
            }
            arr[j + inc] = temp;
            compareCount++;
            moveCount += 3;
        }
        compareCount++;
        moveCount++;
    }


    arr[n] += moveCount;
    arr[n + 1] += compareCount;

    return 0;
}

